Composite and Visitor Example - Tables and Expressions

1. Composite and Visitor Introduction

Composite and Visitor are closely related patterns. The Composite pattern proposes a way to organize a tree structure or a "part - whole" structure. A Visitor implements a single operation, manipulation of an object structure - very often an concrete Composite structure - without affecting the code of the composite structure.

In the example we will create a Table with rows, cells and text content, illustrating the Composite pattern and Visitors that create a HTML representation of the table, one that checks each row has the same number of cells, etc.

2. Composite

2.1. Introduction

The visitor pattern as defined in the GoF book

Compose objects into tree structures to represent part-whole hierarchies. Composite lets clients treat individual objects and compositions of objects uniformly.

Composite is widely used and seems very natural one once we learned about it. The main point is that it decouples the client from the complexity of the structure - whether we have a table with 1 row or 200, 1 cell or 1000 is irrelevant as far as the client is concerned.

An aspect that is not immediately apparent with the table example is the "treat individual objects and compositions of objects uniformly" . Well, in our implementation a cell can contain another table, and a client should not worry about that fact. Later with the visitors, more concrete examples will appear.

This diagram shows the different classes in this example. The method appendTo(Appendable out) is the functionality we care about now, the accept(MVisitor visitor) is important for the next pattern - Visitor - only.

A Composite Example - class diagram

2.2. Code

Some simplifications are done to keep everything as simple as possible. There are no restrictions when adding Text to a Row or a Cell to a Table , some of the vistors later on might have some problems with that. If you want to correct that I would suggest making the addChild(MObject child) method protected and provide methods like addCell(Cell child) etc. to each composite class as appropriate. An alternative is to make a visitor that checks the structure for inconsistencies. Another alternative is to override the addChild(MObject child) method and throw an IllegalArgumentException when inappropriate children are added.

MObject is the root class and defines the only public methods a client might use: accept(MVisitor visitor) and appendTo(Appendable out)

package be.ooxs.examples.designpatterns.composite;

import java.io.IOException;

public abstract class MObject {
	protected abstract void localAccept(MVisitor visitor);

	public abstract void accept(MVisitor visitor);

	public abstract Appendable appendTo(Appendable out) throws IOException;
}

Here is a unit test illustrating how a table is constructed and how the appendTo(Appendable out) method works, before we look at the concrete subclasses.

package be.ooxs.examples.designpatterns.composite;

import static org.junit.Assert.assertEquals;

import java.io.IOException;

import org.junit.Before;
import org.junit.Test;

public class UTestMObject {
	Table table;
	Row r1;
	Row r2;
	Row r3;
	Cell c11;
	Cell c12;
	Cell c21;
	Cell c22;
	Cell c31;
	Cell c32;

	@Before
	public void setUpTable3x2() {
		table = new Table();
		r1 = new Row();
		r2 = new Row();
		r3 = new Row();
		c11 = new Cell();
		c12 = new Cell();
		c21 = new Cell();
		c22 = new Cell();
		c31 = new Cell();
		c32 = new Cell();
		table.addChild(r1);
		table.addChild(r2);
		table.addChild(r3);
		r1.addChild(c11);
		r1.addChild(c12);
		r2.addChild(c21);
		r2.addChild(c22);
		r3.addChild(c31);
		r3.addChild(c32);
	}

	@Test
	public void testAppendTo() throws IOException {
		c11.addChild(new Text("C11"));
		c12.addChild(new Text("C12"));
		c21.addChild(new Text("C21"));
		c22.addChild(new Text("C22"));
		c31.addChild(new Text("C31"));
		c32.addChild(new Text("C32"));

		assertEquals("|C12|", doAppend(c12));
		assertEquals("|C22|", doAppend(c22));

		assertEquals("\n||C31||C32||", doAppend(r3));

		table.appendTo(System.out);
	}

	private String doAppend(MObject component) throws IOException {
		StringBuffer b = new StringBuffer();
		component.appendTo(b);
		String x = b.toString();
		return x;
	}
}

The output to System.out looks like this:

+------------------------------+
||C11||C12||
||C21||C22||
||C31||C32||
+------------------------------+

package be.ooxs.examples.designpatterns.composite;

public abstract class MLeaf extends MObject {

	@Override
	public final void accept(MVisitor visitor) {
		visitor.enter(this);
		localAccept(visitor);
		visitor.leave(this);
	}

}

MComposite is the common ancestor class for for all composite classes. It manages the child components.

package be.ooxs.examples.designpatterns.composite;

import java.util.ArrayList;
import java.util.List;

public abstract class MComposite extends MObject {

	private List<MObject> children = new ArrayList<MObject>();

	protected List<MObject> children() {
		return children;
	}

	public void addChild(MObject child) {
		children.add(child);
	}

	@Override
	public final void accept(MVisitor visitor) {
		visitor.enter(this);
		localAccept(visitor);
		for (MObject child : children) {
			child.accept(visitor);
		}
		visitor.leave(this);
	}
}

This is the only leaf class, and represents textual content of a cell.

package be.ooxs.examples.designpatterns.composite;

import java.io.IOException;

public class Text extends MLeaf {
	private String text;

	public Text(String text) {
		this.text = text;
	}

	public String getText() {
		return text;
	}

	public void setText(String text) {
		this.text = text;
	}

	@Override
	protected void localAccept(MVisitor visitor) {
		visitor.visit(this);
	}

	@Override
	public Appendable appendTo(Appendable out) throws IOException {
		return out.append(text);
	}
}

The actual composite classes are rather simple. Here is the Table

package be.ooxs.examples.designpatterns.composite;

import java.io.IOException;

public class Table extends MComposite {

	@Override
	protected void localAccept(MVisitor visitor) {
		visitor.visit(this);
	}

	@Override
	public Appendable appendTo(Appendable out) throws IOException {
		out.append("\n+------------------------------+");
		for (MObject child : children()) {
			child.appendTo(out);
		}
		out.append("\n+------------------------------+");
		return out;
	}
}

Here is the Row

package be.ooxs.examples.designpatterns.composite;

import java.io.IOException;

public class Row extends MComposite {

	@Override
	protected void localAccept(MVisitor visitor) {
		visitor.visit(this);
	}

	@Override
	public Appendable appendTo(Appendable out) throws IOException {
		out.append("\n|");
		for (MObject child : children()) {
			child.appendTo(out);
		}
		out.append("|");
		return out;
	}
}

Here is the Cell

package be.ooxs.examples.designpatterns.composite;

import java.io.IOException;

import be.ooxs.examples.designpatterns.interpreter.NExpression;

public class Cell extends MComposite {
	private NExpression expression = null;
	private String ref;

	@Override
	protected void localAccept(MVisitor visitor) {
		visitor.visit(this);
	}

	public NExpression getExpression() {
		return expression;
	}

	public void setExpression(NExpression expression) {
		this.expression = expression;
	}

	public String getRef() {
		return ref;
	}

	public void setRef(String ref) {
		this.ref = ref;
	}

	@Override
	public Appendable appendTo(Appendable out) throws IOException {
		out.append("|");
		for (MObject child : children()) {
			child.appendTo(out);
		}
		out.append("|");
		return out;
	}

}

3. Visitor

3.1. Introduction

The visitor pattern as defined in the GoF book

Represents an operation to be performed on the elements of an object structure. Visitor lets you define a new operation without changing the classes of the elements on which it operates.

In other words, separate behavior (Visitor) from structure (Composite) freeing you from complexity. The advantages are more apparent when multiple operations (Visitor) are implemented and you try to imagine all the different unrelated methods that would be necessary somewhere in the MObject (Composite) class hierarchy.

Once the basic infrastructure in the MObject hierarchy is implemented (the accept(MVisitor) method and the internal localAccept(MVisitor) that is my particular way of doing that) everything revolves around the fact that each visit(...) is called once for each node in the composite tree. In our case in a depth first traversal of the tree.

3.2. Code

3.2.1. Visitor Interface

The basic specification of the visitor is best done as an interface. It offers the most flexibility for implementations.

I personally like to add the enter(MObject node) and leave(MObject node) since they make it very simple to do something for each node in the tree (e.g. count total number of nodes) and being able to close certain action when leaving the node is often needed too. For each concrete node type, there should be exactly one visit(...) method.

In certain situations - an abundance of concrete classes that do not all need to be treated differently - a case can be made for providing a visit(...) method for abstract ancestor classes (e.g. MLeaf) but each concrete subclass should only pass muster for exactly one such method.

package be.ooxs.examples.designpatterns.composite;

public interface MVisitor {
	public void enter(MObject node);

	public void leave(MObject node);

	public void visit(Table node);

	public void visit(Row node);

	public void visit(Cell node);

	public void visit(Text node);
}

Sun introduced java.awt.event.MouseListener and java.awt.event.MouseAdapter as a pair of interface with a class providing empty implementations for each method. This allows for subclasses that need to implement only one or two methods without providing empty methods for all the rest.

We follow the same naming convention here, although the GoF Adapter pattern has not much to do with it.

package be.ooxs.examples.designpatterns.composite;

public class MVisitorAdapter implements MVisitor {

	@Override
	public void visit(Table node) {
	}

	@Override
	public void visit(Row node) {
	}

	@Override
	public void visit(Cell node) {
	}

	@Override
	public void visit(Text node) {
	}

	@Override
	public void enter(MObject node) {
	}

	@Override
	public void leave(MObject node) {
	}

}

3.2.2. Reference Creation Visitor

Our first concrete visitor is the simplest. It creates a cell name similar to what happens in a typical spreadsheet, although the format is a little different. In a table with 3 rows and 5 columns, the last cell would have a reference "1!$3$5"

Let's peek at the test methods first:

	@Test
	public void testReferenceCreation() throws IOException {
		MVisitor visitor = new ReferenceCreationVisitor();
		table.accept(visitor);
		assertEquals("1!$2$2", c22.getRef());
	}

And here is the visitor:

package be.ooxs.examples.designpatterns.composite;

public class ReferenceCreationVisitor extends MVisitorAdapter {
	private int tableCount = 0;
	private int rowCount = 0;
	private int cellCount = 0;

	@Override
	public void visit(Cell node) {
		cellCount++;
		String ref = "" + tableCount + "!$" + rowCount + "$" + cellCount;
		node.setRef(ref);
	}

	@Override
	public void visit(Row node) {
		rowCount++;
		cellCount = 0;
	}

	@Override
	public void visit(Table node) {
		tableCount++;
		rowCount = 0;
	}

}

3.2.3. Check Table Visitor

The next example is a little more complex. It checks that each row has the same number of cells, first take a look at the test methods

	@Test
	public void testCheckTableSimple_OK() throws IOException {
		CheckTableVisitorSimple visitor = new CheckTableVisitorSimple();
		table.accept(visitor);
		visitor.reportSquarenessProblem(System.out);
		assertTrue(visitor.checkSquareness());
	}

	@Test
	public void testCheckTableSimple_FAIL() throws IOException {
		//make not square
		Cell badCell23 = new Cell();
		r2.addChild(badCell23);

		CheckTableVisitorSimple visitor = new CheckTableVisitorSimple();
		table.accept(visitor);
		visitor.reportSquarenessProblem(System.out);
		assertFalse(visitor.checkSquareness());
	}

And the visitor's code is here:

package be.ooxs.examples.designpatterns.composite;

import java.io.IOException;

public class CheckTableVisitorSimple extends MVisitorAdapter {
	private int countCells = -1;
	private int previousRowCellcount = -1;
	private boolean errorEncountered = false;

	@Override
	public void visit(Cell node) {
		countCells++;
		if (previousRowCellcount > 0 && previousRowCellcount < countCells) {
			errorEncountered = true;
		}
	}

	@Override
	public void visit(Row node) {
		if (countCells > -1) { //all but the first row
			previousRowCellcount = countCells;
		}
		countCells = 0;
	}

	public boolean checkSquareness() {
		return !errorEncountered;
	}

	public void reportSquarenessProblem(Appendable out) throws IOException {
		if (checkSquareness()) {
			out.append("\nAll rows have the same number of cells");
		} else {
			out.append("\nERROR! Not all rows have the same number of cells");
		}
	}
}

3.2.4. Check Table Visitor - Improved

The next example is a more elaborate implementation of the previous idea. It shows one of the advantages of the Visitor pattern, in that functionality can change without affecting the base classes of the composite hierarchy.

You could in other words, implement two different checks, completely independent of each other.

The complexity is a result of the fact that we want to report much more information here. Therefore we keep a Map cellCount with as key the number of cells (e.g. 2) and as value a list containing all the rows with that number of cells (e.g. row 1 and 3 because they have two cells while row 2 has three cells, in the testCheckTable_FAIL() example below). When there is a row different from the others, we will have two or more entries inthe map, checkSquareness() uses that fact.

findMostFrequent() uses the map to find the first, longest list of rows (that is not the rows with the most cells, but the rows with the most frequent cell count) and uses that as a baseline to compare the erroneous against. Now we can report more detailed information:

Expecting 5 cells per row.
	Number of rows having 1 cell(s) too much: 1
	Number of rows having 2 cell(s) too much: 1
	Number of rows missing 2 cell(s): 2

In order to clarify how CheckTableVisitor should be used, here are the test methods:

	@Test
	public void testCheckTable_OK() throws IOException {
		CheckTableVisitor visitor = new CheckTableVisitor();
		table.accept(visitor);
		visitor.reportSquarenessProblem(System.out);
		assertTrue(visitor.checkSquareness());
	}

	@Test
	public void testCheckTable_FAIL() throws IOException {
		//make not square
		Cell badCell23 = new Cell();
		r2.addChild(badCell23);

		CheckTableVisitor visitor = new CheckTableVisitor();
		table.accept(visitor);
		assertEquals(new Integer(2), visitor.findMostFrequent().getKey());
		visitor.reportSquarenessProblem(System.out);
		assertFalse(visitor.checkSquareness());
	}

The best way to look at this trying to understand how it works, is to imagine each enter(...) , visit(...) and leave(..) method is called from the outside (without woorrying how that works) and finally look what happens when at last the reportSquareness(Appendable out) method is invoked.

This is the actual sequence, I left out method calls that are not overriden ( visit(Table node), enter(MObject node) etc.

visit(r1)
visit(c11)
leave(c11)
visit(c12)
leave(c12)
leave(r1)
visit(r2)
visit(c21)
leave(c21)
visit(c22)
leave(c22)
leave(r2)
visit(r3)
visit(c31)
leave(c31)
visit(c32)
leave(c32)
leave(r3)
leave(table)

And here is the visitor class:

package be.ooxs.examples.designpatterns.composite;

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class CheckTableVisitor extends MVisitorAdapter {
	private List<Row> rows = new ArrayList<Row>();
	private Map<Integer, List<Row>> cellCount = new TreeMap<Integer, List<Row>>();
	private int countCells = 0;
	private List<String> problems = new ArrayList<String>();

	@Override
	public void visit(Cell node) {
		countCells++;
	}

	@Override
	public void visit(Row node) {
		rows.add(node);
		countCells = 0;
	}

	@Override
	public void leave(MObject node) {
		if (node instanceof Row) {
			setCellCount((Row) node, countCells);
		}
	}

	private void setCellCount(Row node, int count) {
		Integer oCount = new Integer(count);
		if (!cellCount.containsKey(oCount)) {
			cellCount.put(oCount, new ArrayList<Row>());
		}
		cellCount.get(oCount).add(node);
	}

	public boolean checkSquareness() {
		return cellCount.size() <= 1;
	}

	public boolean checkNotEmpty() {
		return !rows.isEmpty();
	}

	public void reportSquarenessProblem(Appendable out) throws IOException {
		if (checkSquareness()) {
			out.append("\nAll rows have the same number of cells");
			return;
		} else {
			Map.Entry<Integer, List<Row>> mostFrequent = findMostFrequent();
			out.append("\nExpecting " + mostFrequent.getKey() + " cells per row.");
			for (Map.Entry<Integer, List<Row>> entry : cellCount.entrySet()) {
				if (entry != mostFrequent) {
					if (entry.getKey() < mostFrequent.getKey()) {
						int difference = mostFrequent.getKey() - entry.getKey();
						out.append("\n\tNumber of rows missing " + difference + " cell(s): " + entry.getValue().size());
					} else {
						int difference = entry.getKey() - mostFrequent.getKey();
						out.append("\n\tNumber of rows having " + difference + " cell(s) too much: " + entry.getValue().size());
					}
				}
			}
		}
	}

	protected Map.Entry<Integer, List<Row>> findMostFrequent() {
		Map.Entry<Integer, List<Row>> mostFrequent = null;
		for (Map.Entry<Integer, List<Row>> entry : cellCount.entrySet()) {
			if (mostFrequent == null) {
				mostFrequent = entry;
			} else if (mostFrequent.getValue().size() < entry.getValue().size()) {
				mostFrequent = entry;
			}
		}
		return mostFrequent;
	}
}

3.2.5. To Html Visitor

The last visitor example generates an xhtml representation for our table. You could easily do something similar to generate another xml document as long as it follows more or less the same basic structure (a table-column-cell model would complicat matters slightly).

This test uses regular expressions in order to validate xml. We could use an assertEquals(String,String) and check for an exact match, but that makes the test rather brittle (i.e. it breaks with every small irrelevant change). We don't want the test to break if we use indentation based on blanks instead of tabs, or if we would leave the pretty printing out altogether.

Here we look in particular to see if one cell is rendered correctly. If you're not proficient in regular expressions, here are a few pointers

"(?s)" makes "." match newlines
"\\s*" is any amount of whitespace. (double '\' is escape sequence for java strings)
".*" matches any string

	@Test
	public void testHtml() throws IOException {
		StringBuilder buffer = new StringBuilder();
		MVisitor visitor = new ToHtmlVisitorSimple(buffer);
		table.accept(visitor);
		System.out.println(buffer);//Bad idea in real world tests
		assertTrue(buffer.toString().matches(
			"(?s).*<table>\\s*<tr>.*<td>\\s*<span>\\s*C32\\s*</span>\\s*</td>\\s*</tr>\\s*</table>.*"));
	}

This serves as an example how we can handle (deep) tree structures be keeping track of only the current path to the root node with the Stack tagNames .

It is a simplified implementation, we could add some support for attributes in the tags. But that would overcomplicate the example so I left it out.

package be.ooxs.examples.designpatterns.composite;

import java.io.IOException;
import java.util.Stack;
import java.util.logging.Level;
import java.util.logging.Logger;

public class ToHtmlVisitorSimple implements MVisitor {
	private Stack<String> tagNames = new Stack<String>();
	private Appendable out;

	public ToHtmlVisitorSimple(Appendable out) {
		this.out = out;
	}

	@Override
	public void enter(MObject node) {
	}

	@Override
	public void leave(MObject node) {
		appendCloseTag();
	}

	@Override
	public void visit(Table node) {
		appendOpenTag("table");
	}

	@Override
	public void visit(Row node) {
		appendOpenTag("tr");
	}

	@Override
	public void visit(Cell node) {
		appendOpenTag("td");
	}

	@Override
	public void visit(Text node) {
		appendOpenTag("span");
		try {
			indent();
			out.append(node.getText());
		} catch (IOException exception) {
			Logger.getLogger("ToHtmlVisitorSimple").log(Level.FINEST, "visit(Text) threw IOException", exception);
			throw new RuntimeException(exception);
		}
	}

	private void appendCloseTag() {
		try {
			indent();
			out.append("</").append(tagNames.pop()).append('>');
		} catch (IOException exception) {
			Logger.getLogger("ToHtmlVisitorSimple").log(Level.FINEST, "appendCloseTag threw IOException", exception);
		}
	}

	private void appendOpenTag(String tagName) {
		try {
			tagNames.push(tagName);
			indent();
			out.append('<').append(tagName).append('>');
		} catch (IOException exception) {
			Logger.getLogger("ToHtmlVisitorSimple").log(Level.FINEST, "appendOpenTag threw IOException", exception);
		}
	}

	private void indent() throws IOException {
		out.append('\n');
		for (int i = 0; i < tagNames.size(); i++) {
			out.append('\t');
		}
	}
}

And here is the output from the test method:

<table>
		<tr>
			<td>
				<span>
				C11
				</span>
			</td>
			<td>
				<span>
				C12
				</span>
			</td>
		</tr>
		<tr>
			<td>
				<span>
				C21
				</span>
			</td>
			<td>
				<span>
				C22
				</span>
			</td>
		</tr>
		<tr>
			<td>
				<span>
				C31
				</span>
			</td>
			<td>
				<span>
				C32
				</span>
			</td>
		</tr>
	</table>